Notes on Hallgren's efficient quantum algorithm for solving Pell's equation

摘要

Pell's equation is x^2-d*y^2=1 where d is a square-free integer and we seekpositive integer solutions x,y>0. Let (x',y') be the smallest solution (i.e.having smallest A=x'+y'sqrt(d)). Lagrange showed that every solution can easilybe constructed from A so given d it suffices to compute A. It is known that Acan be exponentially large in d so just to write down A we need exponentialtime in the input size log d. Hence we introduce the regulator R=ln A and askfor the value of R to n decimal places. The best known classical algorithm hassub-exponential running time O(exp(sqrt(log d)), poly(n)). Hallgren's quantumalgorithm gives the result in polynomial time O(poly(log d),poly(n)) withprobability 1/poly(log d). The idea of the algorithm falls into two parts:using the formalism of algebraic number theory we convert the problem ofsolving Pell's equation into the problem of determining R as the period of afunction on the real numbers. Then we generalise the quantum Fourier transformperiod finding algorithm to work in this situation of an irrational period onthe (not finitely generated) abelian group of real numbers. These notes are intended to be accessible to a reader having no prioracquaintance with algebraic number theory; we give a self contained account ofall the necessary concepts and we give elementary proofs of all the resultsneeded. Then we go on to describe Hallgren's generalisation of the quantumperiod finding algorithm, which provides the efficient computational solutionof Pell's equation in the above sense.